import java.util.LinkedList;
import java.util.Queue;

/**
 * @author LKQ
 * @date 2022/1/3 22:32
 * @description 广度优先遍历
 */
public class Solution {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
        System.out.println(solution.orangeRotting(grid));
    }

    public int orangeRotting(int[][] grid) {
        int ans = -1;
        int m = grid.length, n = grid[0].length;
        // 是否已经遍历过
        boolean[][] isRotting = new boolean[m][n];
        int count = 0;
        for (int[] value : grid) {
            for (int j = 0; j < n; j++) {
                if (value[j] != 1) {
                    count++;
                }
            }
        }
        if (count == m * n) {
            // 0分钟没有新鲜橘子
            return 0;
        }
        // 将烂橘子位置加入Deque
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[] {i, j});
                    isRotting[i][j] = true;
                }
            }
        }
        if (queue.isEmpty()) {
            // 没有烂橘子
            return -1;
        }
        while (!queue.isEmpty()) {
            // 同一时间有多个烂橘子
            int size = queue.size();
            while (size > 0) {
                int[] location = queue.poll();
                int  x = location[0], y = location[1];
                for (int k = 0; k < 4; k++) {
                    int ni = x + dirs[k][0], nj = y + dirs[k][1];
                    if (ni >= 0 && ni < m && nj >=0 && nj < n && !isRotting[ni][nj] && grid[ni][nj] == 1) {
                        queue.offer(new int[]{ni, nj});
                        isRotting[ni][nj] = true;
                        grid[ni][nj] = 2;
                    }
                }
                size--;
            }
            // 时间加一
            ans++;
        }
        // 遍历最终是否还存在新鲜橘子
        for (int[] ints : grid) {
            for (int j = 0; j < n; j++) {
                if (ints[j] == 1) {
                    return -1;
                }
            }
        }
        return ans;
    }
}
